Nếu loại đi khả năng dùng lựa chọn ngẫu nhiên của BPP, ta thu được lớp P. Trong định nghĩa, nếu thay máy Turing bằng máy tính lượng tử, ta thu được lớp BQP.

Thuật toán Monte Carlo là thuật toán ngẫu nhiên thường cho câu trả lời chính xác. Các bài toán trong BPP có thuật toán Monte Carlo chạy trong thời gian đa thức. Ngoài ra, có thuật toán Las Vegas là thuật toán luôn đưa ra câu trả lời chính xác nhưng có thể "thất bại" trong việc tìm ra câu trả lời với xác suất thấp. Các thuật toán Las Vegas với thời gian kì vọng đa thức tạo thành lớp ZPP. Nói cách khác, ZPP bao gồm các bài toán có thuật toán ngẫu nhiên luôn cho câu trả lời chính xác và thời gian kì vọng đa thức. Điều kiện thời gian kì vọng đa thức là yếu hơn điều kiện thời gian đa thức do thuật toán có thể có thời gian chạy lũy thừa, nhưng với xác suất rất thấp.